package com.ww.springboot.boot.algorithm.leetcode2;

import cn.hutool.core.util.ObjectUtil;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2025-06-11 11:28
 */
public class B491非递减子序列 {

    public static void main(String[] args) {
        int[] nums = {100,90,80,70,60,50,60,70,80,90,100};
//        System.out.println(System.currentTimeMillis());
//        findSubsequences(nums);
//        System.out.println(System.currentTimeMillis());
        System.out.println(findSubsequences2(nums));
        //System.out.println(System.currentTimeMillis());
    }


    /**
     * 按照顺序 拼接字符串
     * 拼接条件 当前字符大于上一个字符 同时可以选择拼与不拼 满足条件（不重复,且长度大于2）即可加入集合
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> findSubsequences(int[] nums) {
        List<String> list = new ArrayList<>();
        addData(1, "", list, nums);
        addData(1, "" + nums[0], list, nums);

        if (list.size() == 0) {
            return new ArrayList<>();
        } else {
            List<List<Integer>> result = new ArrayList<>();
            for (String s : list) {
                List<Integer> list1 = new ArrayList<>();
                String[] split = s.split("~");
                for (String ss : split) {
                    list1.add(Integer.parseInt(ss));
                }
                result.add(list1);
            }
            return result;
        }
    }

    private static void addData(int i, String s, List<String> list, int[] nums) {
        if (s.indexOf("~") > 0 && !list.contains(s)) {
            list.add(s);
        }
        if (i > nums.length - 1) {
            return;
        }
        if (s.length() == 0) {
            addData(i + 1, "" + nums[i], list, nums);
            addData(i + 1, "", list, nums);
        } else {
            if (nums[i] >= Integer.parseInt(s.substring(s.lastIndexOf("~") + 1))) {
                addData(i + 1, s + "~" + nums[i], list, nums);
                addData(i + 1, s, list, nums);
            } else {
                addData(i + 1, "", list, nums);
                addData(i + 1, "" + nums[i], list, nums);
            }
        }
    }


    public static List<List<Integer>> findSubsequences2(int[] nums) {
        Set<String> set = new HashSet<>();
        addData2(1, "", set, nums);
        addData2(1, "" + nums[0], set, nums);

        if (set.size() == 0) {
            return new ArrayList<>();
        } else {
            List<List<Integer>> result = new ArrayList<>();
            for (String s : set) {
                List<Integer> list1 = new ArrayList<>();
                String[] split = s.split("~");
                for (String ss : split) {
                    list1.add(Integer.parseInt(ss));
                }
                result.add(list1);
            }
            return result;
        }
    }

    private static void addData2(int i, String s, Set<String> set, int[] nums) {
        if (s.indexOf("~") > 0 && !set.contains(s)) {
            set.add(s);
        }
        if (i > nums.length - 1) {
            return;
        }
        if (s.length() == 0) {
            addData2(i + 1, "" + nums[i], set, nums);
            addData2(i + 1, "", set, nums);
        } else {
            if (nums[i] >= Integer.parseInt(s.substring(s.lastIndexOf("~") + 1))) {
                addData2(i + 1, s + "~" + nums[i], set, nums);
                addData2(i + 1, s, set, nums);
            } else {
                addData2(i + 1, s, set, nums);
                addData2(i + 1, "", set, nums);
                addData2(i + 1, "" + nums[i], set, nums);
            }
        }
    }
}
